package Week4.J0506;

public class 礼物的最大价值 {
    public int maxValue (int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] tmpGrid = new int[n+1][m+1];

        // 初始化数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                tmpGrid[i][j] = grid[i-1][j-1];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                tmpGrid[i][j] += Math.max(tmpGrid[i-1][j], tmpGrid[i][j-1]);
            }
        }

        return tmpGrid[n][m];
    }
}
